//1：二叉树的前序遍历 ：https://leetcode.cn/problems/binary-tree-preorder-traversal/description/?envType=problem-list-v2&envId=binary-tree

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
/*
    void _preorderTraversal_R(TreeNode* cur, vector<int>& vt)
    {
        if (cur)
        {
            vt.push_back(cur->val);
            _preorderTraversal_R(cur->left, vt);//左子树
            _preorderTraversal_R(cur->right, vt);//右子树
        }
    }
*/
    vector<int> preorderTraversal(TreeNode* root) {
        //法1：递归
        /*
        vector<int> vt;
        _preorderTraversal_R(root, vt);
        return vt;
        */

        //法2：迭代
        vector<int> vt;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur || !st.empty())
        {
            //左路节点；左路节点的右子树
            while (cur)
            {
                vt.push_back(cur->val);
                st.push(cur);
                cur = cur->left;
            }
            cur = (st.top())->right;
            st.pop();
        }
        return vt;
    }
};

//2：.字典序最小回文串 ：https://leetcode.cn/problems/lexicographically-smallest-palindrome/description/?envType=problem-list-v2&envId=two-pointers

class Solution {
public:
    string makeSmallestPalindrome(string s) {
        int left = 0, right = s.size() - 1;
        while (left < right)
        {
            if (s[left] != s[right])
            {
                s[left] = s[right] = std::min(s[left], s[right]);
            }
            ++left;
            --right;
        }
        return s;
    }
};
